package leetcode; /**
 * description:
 * author:zt
 * date:2021-08-12
 */

/**
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 *
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 */
public class leetcode74 {
    public boolean searchMatrix(int[][] matrix, int target) {
        int len = matrix[0].length;
        int line = matrix.length;
        for (int i = 0; i < matrix.length; i++) {
            if (target==matrix[i][len-1]) return true;
            else if (target<matrix[i][len-1]) {
                line = i;
                break;
            }
        }
        if (line==matrix.length) return false;
        int L = 0, R = len-1;
        while (L<=R){
            int mid = (L+R)>>1;
            if (matrix[line][mid]==target) return true;
            else if (matrix[line][mid]>target) R = mid-1;
            else if (matrix[line][mid]<target) L = mid+1;
        }
        return false;
    }
}
